题面

思路

DFS+剪枝+Hash

分析

首先肯定是 $dfs$，

看成是一张 $n\times n$ 的比赛表，然后一次 $dfs$ 每场比赛的胜负即可，

主要考虑如何剪枝

可行性剪枝

1、如果当前人赢了所有比赛仍不能达到他的分数，剪枝

2、如果剩下的所有比赛都平所得的总分大于实际总分或者都赢的总分小于实际总分，剪枝

$code$ 如下：

if(b[x]+3*(n-y+1)<a[x]) return 0;
rint res=(n-x-1)*(n-x)/2+(n-y+1);
if(sum+3*res<T||sum+2*res>T) return 0;//T为总分

3、（重点）设在所有比赛中平局的场数为 $l$，任意一方胜利的场数为 $w$，显然有

既然是一个二元一次方程组，就可以解一下，得

这样就可以继续可行性剪枝

当胜利的场数或者平局的场数不足时才做，剪去的时间很客观（但是还是过不了

$code$ 如下：

if(w&&b[x]+3<=a[x]) --w,b[x]+=3,res+=dfs(x,y+1,sum+3),b[x]-=3,++w;
if(l&&b[x]+1<=a[x]&&b[y]+1<=a[y]) {
    ++b[x],++b[y],--l;
        res+=dfs(x,y+1,sum+2);
    --b[x],--b[y],++l;
}
if(w&&b[y]+3<=a[y]&&b[y]+3+3*(n-x+1)) --w,b[y]+=3,res+=dfs(x,y+1,sum+3),b[y]-=3,++w;

改变搜索顺序

将实际分数按从大到小排序后搜索效率更高

记忆化！！！

真·神仙

用 $Hash$ 完成记忆化，用 $map$ 存，每次一个人的所有比赛比完之后，判断一下状态是否已经到达过

$code$ 如下：

if(y>n) {
    for(rint i=x+1;i<=n;++i) c[i]=a[i]-b[i];
    sort(c+x+1,c+n+1);LL key=0;
    for(rint i=x+1;i<=n;i++) key=key*base+c[i];
    if(v.find(key)!=v.end()) return v[key];
    return v[key]=dfs(x+1,x+2,sum);
}

要注意的是：

1、我们 $Hash$ 的是每个人当前分数与实际的分数差

2、$Hash$ 之前排序是因为相同数字是等效的，本质上只不过是将一些数字分成几堆，而如何分，顺序是无关的，因此是等效的

warning

1、$Hash$ 判断有没有出现过是不能用 if(v[key])，因为可能这种情况无解，应用 if(v.find(key)!=v.end()).

2、别忘排序，$Hash$ 的是当前与实际分数的差

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
const LL base=1e9+7;//base的取值28也可以
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,T,a[11],b[11],c[11],w,l;
map<LL,int>v;//一开始想用ull自然溢出的，不过貌似没有什么问题
inline int dfs(rint x,rint y,rint sum) {
    if(x==n) return 1;
    if(b[x]+3*(n-y+1)<a[x]) return 0;//可行性剪枝1
    if(y>n) {//一个人的所有比赛完后Hash，再搜索下一个人
        for(rint i=x+1;i<=n;++i) c[i]=a[i]-b[i];
        sort(c+x+1,c+n+1);LL key=0;
        for(rint i=x+1;i<=n;i++) key=key*base+c[i];
        if(v.find(key)!=v.end()) return v[key];//0也是有可能的，因此不能用if(v[key])
        return v[key]=dfs(x+1,x+2,sum);//注意记录值
    }
    rint res=(n-x-1)*(n-x)/2+(n-y+1);//可行性剪枝2
    if(sum+3*res<T||sum+2*res>T) return 0;res=0;
    if(w&&b[x]+3<=a[x]) --w,b[x]+=3,res+=dfs(x,y+1,sum+3),b[x]-=3,++w;//可行性剪枝3
    if(l&&b[x]+1<=a[x]&&b[y]+1<=a[y]) {
        ++b[x],++b[y],--l;
            res+=dfs(x,y+1,sum+2);
        --b[x],--b[y],++l;
    }
    if(w&&b[y]+3<=a[y]&&b[y]+3+3*(n-x+1)/*可行性剪枝1*/) --w,b[y]+=3,res+=dfs(x,y+1,sum+3),b[y]-=3,++w;
    return res%base;//不要忘记取膜
}
inline bool cmp(rint x,rint y){return x>y;}
int main()
{
    rint i;n=read();
    for(i=1;i<=n;i++) T+=a[i]=read();
    sort(a+1,a+n+1,cmp),w=T-n*(n-1),l=n*(n-1)/2-w;//算出胜场和平场
    printf("%d",dfs(1,2,0));
    return 0;
}

推荐题目

emmm 双倍经验 ~强化版 Luogu P3154 [HNOI2013]比赛

devil.